package leetcode.editor.day;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

// 761. 特殊的二进制序列
// https://leetcode.cn/problems/special-binary-string/
class SpecialBinaryString {
    public static void main(String[] args) {
        Solution solution = new SpecialBinaryString().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String makeLargestSpecial(String s) {
            if (s == null && s.length() == 1) return "";
            return dfs(s, 0, s.length() - 1);
        }

        // 回溯，将1类比为 ( ，0类比为 ) ，如果括号匹配，将1都排在前面
        public String dfs(String s, int start, int end) {
            if (end < start) {
                return "";
            }

            List<String> list = new LinkedList<>();
            int count = 0;  // 括号计数
            int pre = start;    // 记录起始位置
            for (int i = start; i <= end; i++) {
                if (s.charAt(i) == '1') {
                    count++;
                } else {
                    count--;
                    // 如果找到一个匹配的情况
                    // 递归，将中间的字符串也进行同样的处理
                    if (count == 0) {
                        // 对子串做相同的操作
                        list.add('1' + dfs(s, pre + 1, i - 1) + '0');
                        // 更新起始位置
                        pre = i + 1;
                    }
                }

                // 进行降序排序
                Collections.sort(list, (a, b) -> b.compareTo(a));
            }

            // 合并list
            return String.join("", list);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
